<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

    <script>
        //创建列表类
        class ArrayList {
            //属性
            constructor() {
                this.array = []
            }
            //方法
            //将我们的数据插入到数组中的方法
            insert(item) {
                this.array.push(item)
            }

            //toString方法
            toString() {
                return this.array.join('-');
            }

            //交换两个位置的数据
            swap(m, n) {
                let temp = this.array[m];
                this.array[m] = this.array[n];
                this.array[n] = temp;
            }

            //实现排序算法
            //冒泡排序
            bubbleSort() {
                var length = this.array.length;
                for (var j = length - 1; j >= 0; j--) {
                    for (var i = 0; i < j; i++) {
                        if (this.array[i] > this.array[i + 1]) {
                            this.swap(i, i + 1);
                        }
                    }
                }
            }
            //选择排序
            selectionSort() {
                //1.获取数组的长度
                var length = this.array.length;
                //2.外层循环
                for (let j = 0; j < length - 1; j++) {
                    var min = j;
                    //2.1内层循环
                    for (let i = min + 1; i < length; i++) {
                        if (this.array[min] > this.array[i]) {
                            min = i;
                        }
                    }
                    this.swap(min, j)
                }
            }
            //插入排序
            insertionSort() {
                //1.获取数组长度
                let length = this.array.length;
                //2.外层循环：从第一个位置开始获取我们的数据，向前面局部有序进行插入
                for (let i = 1; i < length; i++) {
                    //3.内层循环：获取i位置的元素，和前面的数据依次进行比较
                    var temp = this.array[i]
                    var j = i;
                    while (this.array[j - 1] > temp && j > 0) {
                        this.array[j] = this.array[j - 1];
                        j--;
                    }
                    //4.将j位置的数据，放置temp就可以了
                    this.array[j] = temp;
                }
            }
            //希尔排序
            shellSort() {
                //1.获取数组的长度
                let length = this.array.length;
                //2.初始化的增量(gap -> 间隔)
                let gap = Math.floor(length / 2);//向下取整 4
                //3.while循环(gap不断减小)
                while (gap >= 1) {
                    // debugger;
                    //4.以gap作为间隔，进行分组，对分组进行插入排序
                    for (let i = gap; i < length; i++) {
                        let temp = this.array[i]
                        let j = i;
                        while (this.array[j - gap] > temp && j > gap - 1) {
                            this.array[j] = this.array[j - gap];  
                            j = j - gap; 
                        }
                        //5.将j位置的元素赋值temp
                        this.array[j] = temp;
                    }
                    gap = Math.floor(gap / 2);
                }
            }
            // [66, 88, 12, 87, 100, 5, 566, 23]
            // [66, 5, 12, 87, 100, 88, 566, 23] gap = 4
            // [12, 5, 66, 23, 100, 87, 566, 88] gap = 2
            // [66, 88, 12, 87, 100, 88, 566, 23] gap = 1

            //快速排序
            //1.选择枢纽
            median(left, right) {
                //1.取出中间位置
                let center = Math.floor((left + right) / 2);
                //2.判断大小，并且进行交换
                if(this.array[left] > this.array[center]) {
                    this.swap(left, center);
                } 
                if(this.array[left] > this.array[right]) {
                    this.swap(left, right);
                }
                if(this.array[center] > this.array[right]) {
                    this.swap(right, center);
                }
                //3.将center换到right - 1的位置
                this.swap(center, right - 1)

                return this.array[right - 1]
            }
            //2.快速排序的实现
            quickSort() {
                this.quick(0, this.array.length - 1)
            }
            //快速排序递归
            quick(left, right) {
                //1.结束条件
                // debugger;
                if(left >= right) return;
                //2.获取枢纽
                let pivot = this.median(left, right);
                //3.定义变量，用于记录当前找到的位置
                let i = left;

                let j = right - 1;
                //4.进行交换
                while(i < j) {
                    while(this.array[++i] < pivot) {};
                    while(this.array[--j] > pivot) {};
                    if(i < j) {
                        this.swap(i, j);
                    } 
                }
                //6.将枢纽放置在正确的位置
                this.swap(i, right - 1);
                //7.分而治之
                this.quick(left, i - 1);
                this.quick(i + 1,right)
            }


            

        }

        let arrayList = new ArrayList();
        arrayList.insert(66)
        arrayList.insert(88)
        arrayList.insert(12)
        arrayList.insert(87)
        arrayList.insert(100)
        arrayList.insert(5)
        arrayList.insert(566)
        arrayList.insert(23)
        // alert(arraylist) //array: (8) [66, 88, 12, 87, 100, 5, 566, 23]

        ////冒泡排序
        // arrayList.bubbleSort();
        // console.log(arrayList); 

        ////选择排序
        // arrayList.selectionSort();
        // console.log(arrayList);

        ////插入排序
        // arrayList.insertionSort();
        // console.log(arrayList);

        ////希尔排序
        // arrayList.shellSort();
        // console.log(arrayList);

        ////快速排序
        arrayList.quickSort();
        console.log(arrayList);

        let i = [1,2,3,4,5];
        let j = 0;
        while(i[++j] > 3) {
            console.log(j);
        }

    </script>
</body>

</html>